package problem123_Best_Time_to_Buy_and_Sell_Stock_III;

public class Solution {
	public int maxProfit(int[] prices) {
        int[] maxProfitUnitilI=new int[prices.length];
        int min=Integer.MAX_VALUE,max=0;
        for(int i=0;i<prices.length;i++){
        	if(prices[i]<min)
        		min=prices[i];
        	else
        		max=Math.max(max, prices[i]-min);
        	maxProfitUnitilI[i]=max;
        }
        
        int[] maxProfitFromI=new int[prices.length];
        int high=Integer.MIN_VALUE,max2=0;
        for(int i=maxProfitFromI.length-1;i>=0;i--){
        	if(prices[i]>high)
        		high=prices[i];
        	else
        		max2=Math.max(max2, high-prices[i]);
        	maxProfitFromI[i]=max2;
        }
        
        int max3=0;
        for(int i=0;i<prices.length;i++){
        	max3=Math.max(max3, maxProfitUnitilI[i]+maxProfitFromI[i]);
        }
        return max3;
    }
	
	public static void main(String[] args){
		System.out.println(new Solution().maxProfit(new int[]{2,1,2,0,1}));
	}
}
